#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;

	AVLTreeNode(const pair<K, V>& kv) 
		,_kv(kv)
		:_left(nullptr)
		:_right(nullptr)
		:_parent(nullptr)
		:_bf(0)
	{;
	}
};

template<class T,class V>
class AVLTree 
{
	typedef AVLTreeNode<K,V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root = nullptr) {
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		
		while (cur) {
			if (kv.first < cur->_kv.first) {
				parnet = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first) {
				parernt = cur;
				cur = cur->_right;
			}
			else {
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first < parent->_kv.first) {
			parent->_left = cur;
		}
		else {
			parent->_right = cur;
		}
		while (parent) {
			if (cur == parent->left) {
				parent->_bf--;
			}
			else {
				parent->_bf++;
			}
			if (parent->_bf == 0) {
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) {
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2) {
				if (parent->_bf == -2 && parent->_left->_bf == -1) {
					RotateR(parent);
				}
				else if (parent->_bf == 2 && parent->_right->_bf == 1) {
					RotateL(parent);
				}
				else if (parent->_bf == -2 && parent->_left == 1) {
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && parent->_right == -1) {
					RotateRL(parent);
				}
				else {
					return false;
				}
			}
			else {
				return false;
			}
		}
	}
	void RotateR(Node* parent) {
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		parent->_left = SubLR;
		if (SubLR) {
			SubLR->_parent = parent;
		}

		Node* pparent = parent->_parent;
		SubL->_right = parent;
		parent->_parent = SubL;

		if (pparent == nullptr)
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else {
			if (pparent->_left == parent) {
			pparent->_left = SubL;
			}
			else if (pparent->_right == parent) {
			pparent->_right = SubL;
			}
			SubL->_parent = pparent;
		}
		parent->_bf = SubL->_bf = 0;
	}

	void RotateL(Node* parent) {
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		parent->_right = SubRL;
		if (SubRL) {
			SubRL->_parent = parent;
		}
		Node* pparent = parent->_parent;
		SubR->_left = parent;
		parent->_parent = SubR;

		if (pparent == nullptr) {
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else {
			if (pparent->_left == parent) {
				pparent->_left = SubR;
			}
			else if (pparent->_right == parent) {
				pparent->_right = SubR;
			}
			SubR->_parent = pparent;
		}
		parent->_bf = SubR->_bf = 0;
	}
	void RotateLR(Node* parent) {
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		int bf = SubLR->_bf;
		RotateL(SubL);
		RotateR(parent);
		if (bf == 0) {
			parent->_bf == 0;
			SubLR->_bf == 0;
		}
		else if (bf == -1) {
			parent->_bf == 1;
			SubL->_bf == 0;
			SubLR->_bf == 0;
		}
		else if (bf == 1) {
			parent->_bf = 0;
			SubL->_bf == -1;
			SubLR->_bf == 0;
		}
	}

private:
	Node* _root;
};